Abstract: The standardized Authentication and Key Agreement protocol for 5G networks (5G AKA) have several security and privacy vulnerabilities. In this paper, we propose a novel authentication and key agreement protocol for 5G and beyond that is compatible with the standardized 5G AKA. Our protocol has several privacy and security properties, e.g., perfect forward secrecy, resistance against linkability attacks, and protection against malicious SNs. Moreover, both the user identity protection and the perfect forward secrecy are handled using Key Encapsulation Mechanisms (KEM), which makes our protocol adaptable to the quantum-safe setting. To analyze the performance of the proposed protocol, we use the post-quantum KEM CRYSTALS-Kyber, recently chosen to be standardized by NIST, and NIST post-quantum Round 4 candidate KEMs. The results for communication and computation costs show that utilizing our protocol is feasible in practice and sometimes outperforms the public-key cryptography used in 5G AKA, i.e., ECIES. We further prove the security of our protocol by utilizing ProVerif.