Doing some digging into this I found this which details that this can sometimes happen if your client offers too many ssh keys to a server. Try reconnecting using the ssh command with the -v flag so it will print the details of it's attempt to the console. This should provide some additional insight on what is happening.