Design of anonymous authentication scheme is one of the most important challenges in Vehicular Ad hoc Networks (VANET). Most of the existing schemes have high computational and communication overhead and they do not meet security requirements. Recently, Azees et al. have introduced an Efficient Anonymous Authentication with Conditional Privacy-Preserving (EAAP) scheme for VANET and claimed that it is secure. In this paper, we show that this protocol is vulnerable against replay attack, impersonation attack and message modification attack. Also, we show that the messages sent by a vehicle are linkable. Therefore, an adversary can easily track the vehicles. In addition, it is shown that vehicles face with some problems when they enter in a new Trusted Authority (TA) range. As a solution, we propose a new authentication protocol which is more secure than EAAP protocol without increasing its computational and communication overhead.