Bring up a new W2019 Sever for AADConnect ( Not 2016 - its not supported soon!)
https://learn.microsoft.com/en-us/azure/active-directory/hybrid/how-to-connect-install-prerequisites
Do a swing migration:
https://learn.microsoft.com/en-us/azure/active-directory/hybrid/how-to-upgrade-previous-version
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://learn.microsoft.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://learn.microsoft.com/en-us/exchange/exchange-deployment-assistant?view=exchserver-2019
To upgrade the DCs:
https://learn.microsoft.com/en-us/windows-server/identity/ad-ds/deploy/upgrade-domain-controllers