LTE’s success as a high throughput, and umbrella technology for wireless networks is highly affected by the researchers’ capability of solving its current security vulnerabilities. Mutual authentication was adopted by mobile networks to overcome vulnerabilities exploited by “IMSI catcher” and other active attacks. 3GPP’s mutual authentication implementation in EPS AKA succeeded in enhancing the network’s security, but failed to cover weaknesses inherited from its predecessor (UMTS). One of those vulnerabilities is the passive capturing of IMSIs during user identification in the Authentication and Key Agreement protocol. Many researchers tried over the past years, to propose an alternative for EPS AKA, able to ensure high levels of security and offer acceptable QoS performance. In this paper, we will crypt-analyze (SPAKA and PBKP) which was claimed to solve EPS AKA’s privacy and mutual authentication weaknesses, then we will compare its QoS performance to EC-AKA and EPS AKA. Our proposed protocol “EC-AKA” is a real candidate to replace the current authentication and Key Agreement protocol, because of its excellent performance in all the studied parameters.