Upon further troubleshooting, I was able to figure out that our GC is also not working. This is due to port 3268 not available. The issue cannot be fixed by restarting the device and the only resolution is restarting the NETLOGON service.
With port 3268 fixed, I was able to connect our on-prem AD to Azure AD using AAD Connect.