Hi @tim Bouw
Yes, it's better to clean up the virus firstly to avoid infecting other servers or clients in your domain. Is your current server still accessible and working normally?
If yes, you could simply install a new Exchange 2016 server in your environment then move the mailboxes from the old server to the new one. Then decomission the old server.
Here is a related link for your reference: Performing a Like for Like Exchange Server Migration
Please Note: Since the web site is not hosted by Microsoft, the link may change without notice. Microsoft does not guarantee the accuracy of this information.
Otherwise you could also consider Recover Exchange servers
If an Answer is helpful, please click "Accept Answer" and upvote it.
Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.