The remote health monitoring system enables a doctor to diagnose and monitor health problems anywhere for a patient. However, since the patient health information is very sensitive and the Internet is unsecure and prone to many attacks, data can be easily compromised by adversaries. Worse, the mobile phone is also easy to be compromised. Clearly, these issues have brought different privacy and security requirements in wireless healthcare. To address these challenging issues, in this paper, we propose an efficient privacy-preserving authentication scheme with adaptive key evolution, which can prevent illegal access to the patient’s vital signs. Furthermore, we model the leakage process of the key information to set proper key renewal interval, which can adaptively control the key evolution to balance the trade-off between the communication efficiency and security level. The security analysis demonstrates that our scheme can achieve authenticated key agreement, perfect and strong key insulation, privacy preservation, and other important security goals, e.g. authenticity, integrity and freshness of transmitted messages. The performance evaluation shows that our scheme is computationally efficient for the typical mobile phone with limited resources, and it has low communication overhead.