Telecare Medical Information System (TMIS) is a platform for the patients and the medical server to communicate and exchange data through the Internet. As the Internet is an insecure medium, the shared sensitive data is at troublesome situation. To protect sensitive data over the public network, it is essential to have secure communication. The authentication and key establishment protocol supports building a secure communication between the patients and the medical server. Recently, Madhusudhan-Nayak proposed an enhanced chaotic map-based authentication and key establishment protocol for TMIS. In this work, we demonstrate that the Madhusudhan-Nayak scheme does not provide user anonymity, fails to achieve mutual authentication and susceptible to traceability attack, insider attack, server impersonation attack and replay attack. To overcome the weaknesses found in Madhusudhan-Nayak protocol, we propose an improved mutual authentication scheme suitable for TMIS with key establishment technique. The proposed protocol is analyzed against many security threats informally and using the formal method BAN logic, the protocol is proven to be mutually authenticated. As there are numerous authentication protocols for TMIS have been put forward in the literature, we compared the proposed scheme with the related existing schemes in several security aspects. The comparison results illustrate that the proposed protocol surpasses these competing schemes.