With significant technological advancements in Intelligent Transportation Systems (ITS), Electric Vehicles (EVs) or e-vehicles have become increasingly prevalent in the automotive industry due to their low cost and convenience. EVs include complex software, sensors, connectivity, and data-driven systems. However, security and privacy are considered the main concerns that need to be addressed to ensure the safety of drivers, passengers, and surrounding infrastructure, which can lead to various potential security risks or breaches of privacy in EVs. Taking into account these issues, we have proposed a Privacy-preserving Authentication Scheme for Electric Vehicles (called P2AS-EV), which preserves the features of anonymity and unlinkability. The proposed P2AS-EV scheme uses cryptographic primitives, namely XOR, a secure one-way hash, an Elliptic Curve Cryptosystem (ECC), and a Physically Unclonable Function (PUF) to achieve higher security. The informal security analysis shows that the proposed P2AS-EV protocol is more robust and resistant to several known attacks than the competitive schemes. The formal security analysis is also carried out using a well-known Random-OR-Real (ROR) oracle model. Performance analysis shows that the proposed P2AS-EV scheme incurs a computational overhead of 43.6224 ms and a communication overhead of 2176 bits. These values are lower than those of existing approaches, which yield an aggregate improvement of 78.57% in computation cost and an average improvement of 34.68% in communication cost. The formal security verification using the automated validation tool, known as Scyther, confirms that no security attack is possible within bounds. Thus, our scheme outperforms in terms of security and performance and is practically suitable for real-world e-vehicle applications.