Given that you still have the original key, you can generate a CSR from that key, e.g. with:
openssl req -new -key key.pem -config config.cnf -subj "/CN=smtp.example.com" -out csr.pem
where the config.cnf file specifies any additional subject alternative names you might need. You can then use that CSR to get a new certificate for the same key. When you want to switch keys, you generate a new key manually, publish a second TLSA record for the new key, wait for that to age a bit (a few DNS TTLs), and then use “–csr” with a CSR for that key.
You should also consider the approach recommended in my ICANN61 slides: http://imrryr.org/~viktor/ICANN61-viktor.pdf and audio at http://imrryr.org/~viktor/icann61-viktor.mp3