Yesterday I created an SSH key for a new machine. Today I try to log in to a different machine, one that actually doesn’t use keys, and I got the error mentioned in the title. It turns out SSH offers all available keys by default, so I ran out of login attempts before I noticed it.

The solution is simple: Add

IdentitiesOnly yes

to your ~/.ssh/config file.

A more detailed explanation can be found here.