More than ever, the healthcare industry witnesses a remarkable transformation with cloud computing becoming a new data-driven era involving healthcare delivery. However, existing methodologies lean heavily on classical encryption algorithms but will alter with emerging and new security threats. This work lies the exhibition of a new paradigm involving NTRU, (N-th degree truncated polynomial ring units), a post-quantum key generation method, and salsa20 for fast data encryption. The entire process involves the generation of keys from the NTRU polynomial-based private-public key pairs and the actual encryption of data using the salsa20 keystream in order for secure data storage inside the cloud environment. The encrypted data is uploaded to the cloud, and decryption is carried out by the authorized receivers using the complete key and the nonce. Results indicated a relationship between the cryptographic processing time, which gradually increased from 2200 ms for a 75-bit key to 3500 ms for a 250-bit key. Further, encryption time went from 2000 ms for a 50-bit key to 16,000 ms for a 300-bit key, while decryption time was observed between 10 ms for a 500-bit key and over 700 ms for a 3500-bit key. Thus, it provides extra strength against quantum attacks yet also balances the performance and makes it viable for future healthcare data protection.