Why does ssh login as an AD user with private key in nfs4 /home succeed on the second attempt?

Let's first look at how NFS with sec=sys handles this, and then we'll see why NFS with sec=krb5* security fails. In this example, we'll have an SSH server and an NFS server running on two different computers.

The SSH daemon generally runs as root on the SSH server. Assuming your NFS server is configured to squash root, and your home directory is only readable by you, the SSH daemon running as root would not be allowed to read the public key stored in your home directory. When the SSH server needs to examine the public key, it spawns another process as the user you're trying to log in as, where that user then has permission to read the public key file. The user is then able to log in if they possess the correct private key.

This method works fine for NFS with sec=sys, as the computer tells the NFS server who is connecting, and the NFS server blindly trusts it.

Now we'll look at sec=krb5*. In this security model, the NFS server requires that the client present a ticket confirming their identity. Lets assume you haven't logged into the SSH server yet. Just as before, the root account is not able to read the SSH public key. But unlike before, spawning a process as the correct user does not help, as user does not possess an NFS service ticket or a TGT. This authentication method then fails and the SSH daemon tries to use another authentication method like password.

Now after authenticating with the password, you've picked up a Kerberos TGT, and possibly an NFS service ticket. After logging out, my guess is that the credential cache is still valid on the SSH server. When attempting to log back in again, this time after the SSH daemon spawns a process as the user, it is able to read the public key, as it still has valid credentials for that user.

Hope this helps!