The Long-Term Evolution (LTE)/5G network connects much of the world’s population to provide subscriber’s voice calls and mobile data delivery, with security provided by the Authentication and Key Agreement (AKA) defined by 3GPP, which makes the LTE/5G network more secure than all its predecessors. Primarily due to the access limitations of LTE systems, the vulnerabilities of AKA protocol and potential attacks have not received much investigation, which is essential to LTE users with a tremendous amount of cellular services. In this study, we focus on two questions: (i) what are the vulnerabilities that can be exploited to carry out attacks in practice? and (ii) how to design an enhanced AKA protocol against such attacks? We examine the detailed procedures of Evolved Packet System (EPS)-AKA protocol by 3GPP, and have identified three types of attacks with respect to catching, location tracking, and jamming. We have designed and implemented attacks with commercial equipment to evaluate their threats in practice. In addition, we propose an enhanced AKA protocol that essentially relies on asymmetric encryption rather than symmetric in the AKA protocol and additional digital signatures to countermeasure these attacks. Finally, we verified our solution through formal verification to prove that our solution can mitigate the newly found vulnerabilities.