Recently, the Third Generation Partnership Project (3GPP) has initiated to work in the Fifth Generation (5G) network to fulfill the security characteristics of IoT-based services. 3GPP has proposed the 5G handover key structure and framework in a recently published technical report. In this paper, we evaluate the handover authentication methodologies available in the literature and identify the security vulnerabilities such as violation of global base-station, failure of key forward/backward secrecy, de-synchronization attack, and huge network congestion. Also, these protocols suffer from high bandwidth consumption that doesn’t suitable for energy efficient mobile devices in 5G network. To overcome these concerns, we introduce Secrecy and Efficiency Aware Inter-gNB (SEAI) handover Authentication and Key Agreement (AKA) protocol. The formal security proof of the protocol is carried out by random oracle model to achieve the session key secrecy, confidentiality, and integrity. For the protocol correctness and achieve the mutual authentication property, simulation is performed using the AVISPA tool. Also, the informal security evaluation represents that the protocol defeats all the possible attacks and achieves the necessary security properties. Moreover, the performance evaluation of the earlier 5G handover protocols and proposed SEAI protocol is carried out. From the evaluations, the significant results are obtained based on computation, transmission, and communication overhead.