Authentication Order with SSH

The ssh server decides which authentication options it allows, the ssh client can be configured to decide in which order to try them.

The ssh client uses the PreferredAuthentications option in the ssh config file to determine this.

From man ssh_config (see it online here):

PreferredAuthentications
             Specifies the order in which the client should try protocol 2 authentication methods.  This allows a client to prefer
             one method (e.g. keyboard-interactive) over another method (e.g. password).  The default is:

                   gssapi-with-mic,hostbased,publickey,
                   keyboard-interactive,password

I don't believe it's possible, without playing with the source, to tell the OpenSSH server to prefer a certain order - if you think about it, it doesn't quite make sense anyway.

Adding this:

PreferredAuthentications keyboard-interactive,password,publickey,hostbased,gssapi-with-mic

...to my /etc/ssh/ssh_config helped me to solve this, and saved a lot of time too!

You can check if it works by using ssh -v user@host command to connect, where -v stands for "verbose".

Adding to the other two answers already mentioning the PreferredAuthentications option, I'd like to add you don't need to edit any file to set this setting if you don't want. Rather, you can just set it at the command-line for an individual call to ssh, with the -o option, as follows:

ssh -o PreferredAuthentications=publickey,gssapi-with-mic,hostbased,keyboard-interactive,password user@hostname

References:

1. To read more about the PreferredAuthentications option, see man ssh_config (see it online here). Also read about the ssh -o option in the man ssh manual pages (online here).