The energy Internet (EI)-based vehicle-to-grid (V2G) technology facilitates the electric vehicles not only to distribute additional electricity into grid systems, but also support receiving back from the power grid in the form of charging. The secure key establishment is quite significant to initiate the bidirectional electricity power delivery into and from the system. To effectively implement any EI-based V2G communication, the authentication protocol must be free from cyber attacks. In this article, we not only explore the drawbacks of several smart grid-based authentication protocols but also bring forth the limitations of a recently presented EI-based V2G scheme by Gope and Sikdar. The examined drawbacks in this protocol may disrupt its proper functioning, since it faces desynchronization problems while logging into the mobile device bearing registration parameters. The scheme is also vulnerable to replay attack and man-in-the-middle attack. The user is also unable to validate session key in the protocol. Considering these limitations, we propose a novel and efficient V2G protocol framework enabling the vehicles to communicate or recharge at desired recharging stations. The results of the proposed framework are compared with several contemporary schemes, and its security features are validated by random oracle model-based formal analysis.