Disclosed are memory encryption systems and methods that rotate encryption keys for robust resistance against side-channel-analysis (SCA)-based attacks on communication paths between an encryption engine within a trust boundary and an external memory component. A key data structure has a plurality of keys that are used to encrypt a plurality of memory blocks in the external memory. The memory blocks encrypted with the oldest key of the key data structure are identified. Encrypted data is read from the identified memory blocks. The encrypted data is decrypted from the identified memory blocks. The data is then re-encrypted using the selected key that is newer than the oldest key, and re-written to the identified memory blocks.