Bring up a new W2019 Sever for AADConnect ( Not 2016 - its not supported soon!)
Do a swing migration:
You can upgrade Exchange 2013 to 2019 at anytime. Exchange 2013 with the latest CU does support W2019 Domain Controllers:
What 2013 DOES not support is being installed on Windows 2019 or 2016:https://video2.skills-academy.com/en-us/exchange/plan-and-deploy/supportability-matrix?view=exchserver-2019#supported-operating-system-platforms
You can use the Exchange Assistant to upgrade to Exchange 2019 on new W2019 servers:
https://video2.skills-academy.com/en-us/exchange/exchange-deployment-assistant?view=exchserver-2019
To upgrade the DCs: