Internet of Medical Things (IoMT) has facilitated the healthcare industry by providing ease of communication among doctors and patients living in remote areas for accomplishing diagnosis, real-time monitoring, and treatment procedure efficiently. The patient’s health-related data must be secured from various attacks of adversary since the data is sensitive and highly prone to attacks. This paper proposes an architecture that suits both localized and emergency scenarios. This architecture utilizes cloud server and edge computing technology. Provably secured lightweight authenticated key agreement protocol for modern health industry (PSLA2P) provides a lightweight authentication and key agreement protocol that can be deployed in the proposed network architecture. It protects the privacy of the patient’s health-related data by providing anonymity and untraceability. Real-Or-Random (ROR) model is used for the formal analysis of PSLA2P. We have verified the security weaknesses of PSLA2P using the Scyther simulator. Moreover, the informal analysis ensures high-level mitigation against known possible attacks. PSLA2P achieves better performance in terms of computation and communication overhead.