If one's key is correctly used to encrypt data, and the key is stolen (that is all physical media containing it are stolen and thus become unavailable; as in "my last bike lock key got stolen"), then one doesn't even have the option to re-encrypt the data: one lost access to it.
If one's key is directly used to encrypt data, and the key is compromised (it's value became known to adversaries, or that's to be feared), then
- if adversaries have access to the database encrypted with the compromised key, then confidentiality of the data was or will be lost irrespective of when that access occurs (e.g. in the future from an old backup)
- otherwise, decrypting the data with the compromised (but still available) key, then re-encrypting the data with a fresh key, restores things to normal.
If re-encryption of all the data is inconvenient because it contains large records (e.g. images or videos), it's possible to cut on that computational cost by indirectly encrypting the data with the key, using two levels of key. Each large record is encrypted with it's individual random record key, itself encrypted with the main key and stored as a small auxiliary record. To access a record in clear, it's read it's auxiliary record, that's decrypted with the main key yielding the record key, and the record itself is decrypted with that record key. For re-encryption following compromise of the main key (only), we only need to decipher and re-encrypt the auxiliary records.
However, that indirect encryption reduces the amount of data adversaries must obtain to make good use of a key compromise: now they only need a copy of the encrypted key records under the old key to make good use of later access to the database. Thus in case of compromise of the the main key, it might be advisable to immediately decrypt and re-encrypt the record keys, then slowly decrypt and re-encrypt each individual record under a fresh random record key. For this purpose, the encrypted key records must come with identification of the version of the main key they are encrypted under.