SSH and kerberos authentication problem AIX 5.3

I've configured an AIX 5.3 client to use our Windows AD for user authentication via Kerberos.
When I try to ssh to the server using the AD credentials, I eventually get access but not after getting prompted for a password 3 times (which doesn't work) followed by an accepted login on the 4th attempt.

The password prompt changes on the 4th attempt (something to do with the authentication method changing from keyboard-interactive to password).

I've attached verbose output from the attempt below (some private info blocked out):

root@utajona2************:/ # ssh -v tso940sa5@utajona2
OpenSSH_5.4p1, OpenSSL 0.9.8m 25 Feb 2010
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: init_func_ptrs success
debug1: Value of krb5 is 1
debug1: Value of gssapi is 1
debug1: Connecting to utajona2 [xxx.xxx.xxx.xxx] port 22.
debug1: Connection established.
debug1: permanently_set_uid: 0/0
debug1: identity file /.ssh/id_rsa type -1
debug1: identity file /.ssh/id_rsa-cert type -1
debug1: identity file /.ssh/id_dsa type 2
debug1: identity file /.ssh/id_dsa-cert type -1
debug1: Remote protocol version 2.0, remote software version OpenSSH_5.4
debug1: match: OpenSSH_5.4 pat OpenSSH*
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_5.4
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: server->client aes128-ctr hmac-md5 none
debug1: kex: client->server aes128-ctr hmac-md5 none
debug1: SSH2_MSG_KEX_DH_GEX_REQUEST(1024<1024<8192) sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_GROUP
debug1: SSH2_MSG_KEX_DH_GEX_INIT sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_REPLY
debug1: Host 'utajona2' is known and matches the RSA host key.
debug1: Found key in /.ssh/known_hosts:9
debug1: ssh_rsa_verify: signature correct
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: SSH2_MSG_NEWKEYS received
debug1: Roaming not allowed by server
debug1: SSH2_MSG_SERVICE_REQUEST sent
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: publickey,password,keyboard-interactive
debug1: Next authentication method: publickey
debug1: Trying private key: /.ssh/id_rsa
debug1: Offering public key: /.ssh/id_dsa
debug1: Authentications that can continue: publickey,password,keyboard-interactive
debug1: Next authentication method: keyboard-interactive
tso940sa5's Password:
debug1: Authentications that can continue: publickey,password,keyboard-interactive
tso940sa5's Password:
debug1: Authentications that can continue: publickey,password,keyboard-interactive
tso940sa5's Password:
debug1: Authentications that can continue: publickey,password,keyboard-interactive
debug1: Next authentication method: password
tso940sa5@utajona2's password:
debug1: Authentication succeeded (password).
debug1: channel 0: new [client-session]
debug1: Requesting no-more-sessions@openssh.com
debug1: Entering interactive session.
6 unsuccessful login attempts since last login.
Last unsuccessful login: Wed 25 May 12:32:40 2011 on ssh
Last login: Wed 25 May 10:51:55 2011 on /dev/pts/1
*******************************************************************************
*                                                                             *
*                                                                             *
*  Welcome to AIX Version 5.3!                                                *
*                                                                             *
*                                                                             *
*  Please see the README file in /usr/lpp/bos for information pertinent to    *
*  this release of the AIX Operating System.                                  *
*                                                                             *
*                                                                             *
*******************************************************************************
$

Thanks.

:wall:

Seems like a config issue, password being configured before key. Check the AllowedAuthentications order in *ssh*config.

We've had the same issue. We use a DNS hostname that round-robin resolves to about 6 different AD servers. Every now the Windows folks would take one of the AD servers down or stop the kerberos service. Then when the hostname resolution took place, if we got an IP for that AD server, we would get failed logins. Our users called and complained that they had to try 4 or 5 times before they were able to get in and they swore they were typing the right password. We resolved it temporarily by specifying a AD server that we knew to be up in the "realms" section of the /etc/krb5/krb5.conf file. Once the AD server was back up, we changed it back.

The trick to a DNS round robbin is to make each machine a DNS server that says is it the one, so the search for a live DNS server skips dead hosts.