Postgres connection establishment slow

My best guess: You're using host name lookups in pg_hba.conf - and it makes PostgreSQL perform DNS queries that fail. You're still able to connect, because it hits a rule further down the road.

You can also try turning off log_hostname on postgresql.conf.

To rule out lookups entirely, you could add the client in the hosts-file of the server.

I had a similar issue. I was trying to connect to local database:

psql -U postgres -h localhost

This was extremely slow for me. Changing localhost to 127.0.0.1 made an immense difference. Connection is instant. Similar issues related to localhost have been reported quite often, e.g. here.