The Authentication Key Agreement Scheme (AKA) of Universal Mobile Telecommunication System (UMTS) provides substantial enhancement to solve the vulnerabilities in GSM and other wireless communication systems. However, we discovered four security weaknesses of UMTS AKA, that is, redirection attack, man-in-the-middle attack, sequence number depletion, and roaming attack. An adversary can launch these attacks to eavesdrop, or cause billing problems. To cope with these problems, a new Secure Authentication Key Agreement Protocol (S-AKA) is proposed in this paper to enhance the security to resist the attacks. To improve the efficiency and redundancy of UMTS AKA, S-AKA reduces both the authentication messages and bandwidth consumption of UMTS AKA. The formal proof of S-AKA is also given to ensure the security strength of S-AKA.