Power Automate/Power Apps - On premise Gateway not listed in Power Apps is causing multiple MS and

We are  unable to see on premises gateway in Power Apps Page and also dropdown in connection wizard is empty.

 

Although gateways are listed in Power Admin center, it is not being reflected in Power Automate using the Power query.

We tried restarting the server, installing new Gateway  and checking region as advised in the trouble shoot guide but unfortunately none of the solutions have worked so far