In the UMTS Authentication and Key Agreement (AKA) protocol only the home network can generateauthentication vectors to its subscribers. Therefore; the home location register and authentication centre(HLR/AuC) actually suffers from the traffic bottleneck. AKA protocol has been enhanced by generatingtemporary key to enable visitor location register (VLR/SGSN) to authenticate mobile station (MS) withoutintervention of HLR/AuC. This proposed protocol called Efficient AKA (E-AKA),The proposed protocol satisfies the security requirements of third generation (3G) mobile networks. In thisresearch paper the current AKA has been enhanced by reducing the network traffic, signalling messagebetween entities. This is achieved by reducing a size n array of authentication vector and the number ofmessages between MS and HLR/AuC. Hence, the traffic for the home network to generate authenticationvectors is exponentially decreased, then reducing the authentication times, and setup time as well asimproving authentication efficiency. Additionally, a mutual authentication between MS and its HomeNetwork (HN) and between an MS and the Serving Network (SN) is achieved. A security analysis andcomparison with related work shows that E-AKA is more efficient and a secure authentication is achieved.