With the rapid popularization of electric vehicles (EVs) in modern society, vehicle-to-grid (V2G) has been widely concerned as an emerging technology. However, various privacy and security issues arise frequently in the energy interaction between EVs and the smart grid (SG), such as the lack of secure authentication and disclosure of EVs’ identity. Although many crypto-based schemes are proposed to achieve secure authentication of V2G networks, they rely on certification authority (CA) or private key generator (PKG). In response to this problem, some certificateless signature-based schemes have been proposed. Nevertheless, most of them are not suitable for V2G networks due to the high computational cost and communication overhead, and they do not consider the problem of tracking illegal signatures. Therefore, we propose a traceable and privacy-preserving authentication scheme with supporting batch verification for energy trading in V2G networks. We use the method of binary tree level traversal to quickly track EVs with illegal signatures, which can reduce computational resources. Besides, the proposed scheme is easier to be deployed in real world because of avoiding the problems of key escrow and certificate management. Finally, we conduct a comprehensive security analysis and performance evaluation regarding our scheme. We prove that our proposed scheme is secure under the random oracle model (ROM), and the experimental results illustrate that the proposed scheme has less computational cost and communication overhead as compared to the existing schemes.