This research work analyzes the universal mobile telecommunication system (UMTS) authentication and key agreement (AKA) protocol, which suffers from the traffic bottleneck at home location register and authentication center (HLR/AuC). In addition, serving network has no capability to authenticate mobile station. To overcome these problems a new security scheme has been proposed which provides a more efficient and a secure authentication between mobile station and home networks, the proposed protocol called Efficient AKA (E-AKA). The E-AKA uses a temporary key to enable visitor location register and serving network (VLR/SN) to authenticate mobile station (MS) without intervention of HLR/AuC. To analyze and validate the security of the proposed protocol, the BAN (Burrows, Abadi and Needham) logic is used. The results show that the E-AKA protocol is more robust than the current AKA protocol.