With the rapid advancement of the Internet of Vehicles (IOV) and the increasing use of 5G networks, ensuring secure and efficient communication between vehicles and infrastructure has become crucial. This paper introduces the design and evaluation of a novel Authentication and Key Agreement (AKA) protocol specifically designed for IOV systems, taking advantage of the strengths of 5G technology. It incorporates advanced cryptographic methods, such as public key infrastructure (PKI), to establish secure communication pathways between vehicles, roadside units (RSUs), and other IOV components. In addition to improving security, the protocol emphasizes efficiency by optimizing message exchanges, lowering computational demands, and reducing communication delays. Formal verification using the AVISPA tool demonstrates that the proposed AKA protocol greatly enhances both the security and efficiency of IOV communications within 5G networks.