In this letter, we investigate the performance of a two-way multi-relay system employing three-phase analog network coding (ANC) with best relay selection over independent and non-identically distributed Nakagami-m fading channels. Specifically, we derive a tight closed-form expression for the overall system outage probability. We also derive an asymptotic outage expression in high signal-to-noise ratio (SNR) regime, from which the diversity order and diversity-multiplexing tradeoff are examined. In addition, we present an optimal relay power allocation to minimize the overall system outage. Numerical and simulation results validate the theoretical analysis and demonstrate the advantages offered by the considered scheme.