No. You can have multiple DKIM DNS records (each identified by an id called selector). Each DKIM signature includes the selector. When you change keys, you create a new DNS entry with a new selector, then change the settings of the mailserver. New mails will then be signed by the new key with the new selector. Old mails can still be verified until you delete the old DNS entry.