A key agreement protocol is a protocol whereby two or more communicating parties can agree on a key or exchange information over an open communication network in such a way that both of them agree on the established session keys for use in subsequent communications. Recently, several key agreement protocols based on chaotic maps are proposed. These protocols require a verification table to verify the legitimacy of a user. Since this approach clearly incurs the risk of tampering and the cost of managing the table and suffers from the stolen-verifier attack, we propose a novel key agreement protocol based on chaotic maps to enhance the security. The proposed protocol not only achieves mutual authentication without verification tables, but also allows users to anonymously interact with the server. Moreover, security of the proposed protocol is modelled and analyzed with Petri nets. Our analysis shows that the proposed protocol can successfully defend replay attacks, forgery attacks, and stolen-verifier attacks.