Implantable medical devices (IMDs) are man-made devices, which can be implanted in the human body to improve the functioning of various organs. The IMDs monitor and treat physiological condition of the human being (for example, monitoring of blood glucose level by insulin pump). The advancement of information and communication technology enhances the communication capabilities of IMDs. In healthcare applications, after mutual authentication, a user (for example, doctor) can access the health data from the IMDs implanted in a patient's body. However, in this kind of communication environment, there are always security and privacy issues, such as leakage of health data and malfunctioning of IMDs by an unauthorized access. To mitigate these issues, in this paper, we propose a new secure remote user authentication scheme for IMDs communication environment to overcome security and privacy issues in existing schemes. We provide the formal security verification using the widely accepted Automated Validation of Internet Security Protocols and Applications tool. We also provide the informal security analysis of the proposed scheme. The formal security verification and informal security analysis prove that the proposed scheme is secure against known attacks. The practical demonstration of the proposed scheme is performed using the broadly accepted NS2 simulation tool. The computation and communication costs of the proposed scheme are also comparable with the existing schemes. Moreover, the scheme provides additional functionality features, such as anonymity, untraceability, and dynamic implantable medical device addition.