The Universal Mobile Telecommunication System (UMTS) adopts 3GPP authentication and key agreement (3GPP AKA) protocol as its security framework, and this protocol has made effective improvements on the hidden security problems of GSM (global system for mobile communications). This paper investigates into the security of the 3GPP authentication and key agreement protocol, and analyzes four types of attacks to which it is vulnerable. To solve the security problems mentioned above, it presents an efficient authentication and key agreement protocol, which is based on public key cryptography, under the circumstances of location updating and location immovability, adopts formal analysis to prove the security of two protocols proposed, and compares it with other protocols from the aspect of security. The results show that this proposed protocol can significantly enhance the security of 3GPP AKA protocol.