The Internet of Medical Things (IoMT) is emerging as a significant domain for healthcare services due to the revolution of the Internet of Things (IoT) paradigm across various industries. However, IoMT systems continue to experience a significant challenge in protecting the security and privacy of sensitive medical data. In this article, a robust key exchange protocol based on the max-product semiring and matrices with powers is introduced. The aim of this research paper is to provide a new cryptographic platform which is more efficient in terms of computational cost and storage without compromising the security. The security of the proposed protocol relies on the fact that solving a system of non-linear equations in a max-product semiring is NP-hard. The protocol exhibits favorable characteristics for IoMT environments, including low computational overhead and reduced communication latency. An algorithm and an example were given to illustrate the protocol. Furthermore, the security and experimental analysis of the key exchange protocol were demonstrated.