Re-encrypting the data-at-rest is going to be prohibitive. 500M records to update will generate tremendous log, a lot of data IO, will last hours if not days, overall will be quite disruptive. Not to mention that an operational error might leave the entire database perfectly encrypted (ie. w/o a key to decrypt it).
What I would recommend is to rotate the keys higher on the key hierarchy:
- Use a symmetric key to encrypt the data.
- Change the symmetric key periodically, eg. once a week generate a new one, encrypt new data with the new one but don't change old data
- encrypt the symmetric keys with a certificate
- use DECRYPTBYKEYAUTOCERT to decrypt the data, which will handle picking the right symmetric key automatically
- when required, rotate the certificate that encrypts the symmetric keys. Symmetric key support multiple certificate encryption, so it is perfectly feasible to add a new certificate, add encryption by the new certificate to all symmetric keys, then drop old certificate
Similar schemes to this are often deployed by large companies. Re-encrypting all the data is seldom done, because is so prohibitive. Using multiple symmetric keys and generating new ones every so often will reduce the amount of possible privacy loss if a symmetric key gets compromised. Rotating the certificate used to decrypt the symmetric keys gives the desired mitigation of certificate compromise as a compromised certificate will not be able to access data after the rotation, even though the data is still encrypted with the same old symmetric keys.
It is true that I can envision an attack on which if I have access to the certificate I can extract all the symmetric key material, then when the certificate rotates, I can in theory use the saved key material to decrypt the data (using means other than SQL Server). But this is no different that saying that 'if I have access to a compromised certificate before is rotated, I can decrypt all the data and save the decrypted data', and this puts the attack in a new light, since no amount of after the fact key rotation will recuperate data that is already lost to the attacker.