We have made some progress. GSSAPI authentication method is taking time though we have not enabled the GSSAPI authentication method in postgres (but the connection request is spending some time there).
When a libpq client sees that krb5 credentials exist, it tries to use them preemptively, without knowing if the server supports them or not. Once given an error, it then tries again without GSS. The server log file should show evidence of these failed connections, and the failure reason given might offer some clues.
But this first try should normally be fast. Is the time taken on the client side, or on the server side? Using strace on a simple psql invocation would be the best way to answer this (on Linux). If the server doesn't support GSS at all, it is hard to see why it should fail slowly on the server side so that would probably be a bug.