New versions of SM allow for multiple keys.
This would allow you to add the second key, add it to DNS, validate, all while the first key is still active. Then you can remove the old key after a few days - the keys are used during delivery only - so once the destination gets all the mail, the old keys are done.
MailEnable survivor / convert --