I understand why this is happening. My ssh-agent is sending multiple keys to the server, and only one of them is good. So it hits the max number of login attempts on the server and disables the login. I know how to fix this from the clientside. However I do not know how to fix this from the server side. So even when my client sends only the one key, I get the failed login attempt. I've tried restarting the service, but that doesn't work. Also all of my google searches talk about how to resolve this from clientside, so my googlefu has failed me. Is there a blacklist that I need to manually edit or something like that?
Most probably, your failed login attempts are registered by pam_tally or pam_tally2. You can check it by calling both programs. Whichever prints you with your counter can be used to reset it:
pam_tally2 --user yourid --reset
assuming that pam_tally2 works for you.
Having a lot of keys in agent is not a good idea. Much better is to define the connection between keys and servers in your .ssh/config, which will avoid such problems. For example:
Host myhost myhost2 IdentityFile ~/.ssh/id_rsa_myhost Host myhost3 myhost4 anotherhost IdentityFile ~/.ssh/id_dsa_another