The session initiation protocol (SIP) is considered as the dominant signaling protocol for calls over the Internet. However, SIP authentication typically uses HTTP digest authentication, which is vulnerable to many forms of known attacks. This paper proposes a new secure authentication and key agreement mechanism based on certificateless public-key cryptography (CL-PKC), named as SAKA, between two previously unknown parties, which provides stronger security assurances for SIP authentication and media stream, and is provably secure in the CK security model. Due to using CL-PKC, SAKA effectively avoids the requirement of a large Public Key Infrastructure and conquers the key escrow problem in previous schemes.