A multi-server retrial queue with a Markovian arrival process, as well as possible customer non-persistency and unreliable operation of servers, is analysed. The service of a customer (transmission of information) consists of a random number of phases. During a transmission, a failure can occur. The failure does not cause server breakdown or its subsequent recovery. The failure occurrence during service of a customer implies either that the departure of the customer from the server (the customer joins an orbit and retries later), the customer re-starts complete service immediately, or the customer resumes the service from the phase at which the failure occurred. The total occupation time of a server by a customer has a so-called PHF (phase-type with failures) distribution. The dynamics of the system are described by a multi-dimensional level-dependent Markov chain. An infinitesimal generator of the chain is derived. To obtain the ergodicity condition, we prove that the Markov chain belongs to the class of asymptotically quasi-Toeplitz Markov chains. Because we consider a multi-server queuing system, the dimensions of the blocks of the generator can be large. Thus, the use of a standard algorithm to find a stationary distribution of an asymptotically quasi-Toeplitz Markov chain can face problems in the stage of computer implementation. We develop a new efficient iterative algorithm for approximate computation of the stationary distribution that computes many times faster and requires much fewer computer resources than the standard algorithm. The advantages of the new algorithm and some features of the model under consideration are numerically demonstrated. © 2018 Elsevier Inc.