The 5G-AKA protocol, defined by 3GPP for authentication and key agreement in 5G networks, remains vulnerable to linkability, synchronization failure, and Sequence Number (SQN) exposure attacks. These issues threaten user privacy and service availability. Existing improvements often retain these flaws or cause high overhead due to continued use of the legacy SQN mechanism from 3G. In this paper, we propose 5G-RNAKA, a secure and efficient AKA protocol for 5G systems. Unlike 5G-AKA, 5G-RNAKA eliminates SQN counters and instead utilizes random numbers generated by the Universal Subscriber Identity Module (USIM) in 5G User Equipment (UE) for session identification. This random number is embedded in the reply message from the service network (SN) to prevent replay attacks against the UE. Additionally, by removing the SQN mechanism, 5G-RNAKA enhances user privacy by preventing attackers from linking challenge-response sessions. It also enables the UE to authenticate the SN, effectively mitigating the risk of SN impersonation. We formally verify that 5G-RNAKA achieves its security goals of privacy, authentication, and secrecy using the state-of-the-art formal verification tool, Tamarin Prover. Our implementation and evaluation further demonstrate that 5G-RNAKA improves communication efficiency and reduces storage overhead. While primarily designed for 5G, 5G-RNAKA's features align with emerging trends in 6G authentication, suggesting its potential for adaptation to future 6G architectures.