Universal Mobile Telecommunication Systems Authentication and Key Agreement (UMTS-AKA) protocol is an enhanced Authentication and Key Agreement (AKA) protocol of Global System for Mobile (GSM) communications. The UMTS-AKA has weaknesses in bandwidth consumption, authentication message overhead and mutual authentication. This paper analyzes UMTS-AKA protocol and proposes a new Enhanced Secured Universal Mobile Telecommunication System Authentication and Key Agreement (ESUMTS-AKA) protocol with additional security features. All the messages exchanged between different entities with International Mobile Subscriber Identity (IMSI) are encrypted so that it would be less vulnerable to attacks. Private keys and public keys of different entities are used during encryption of messages. A temporary key in the proposed ESUMTS-AKA protocol reduces the bandwidth consumption between different entities. The computation of hash functions in Home Network (HN) decreases by increasing the hash functions generated in Serving Network (SN). The proposed ESUMTS-AKA protocol is more secured due to Combined Cipher Key (CCiK) and Combined Integrity Key (CInK). Analysis and simulated results prove that the proposed ESUMTS-AKA protocol is more enhanced and highly protected. © 2019, Springer Science+Business Media, LLC, part of Springer Nature.