Earlier quoted context omitted.
> Rate limiting You don't need fail2ban to rate-limit SSH. RFTM ... MaxStartups, PerSourceMaxStartups, PerSourceNetBlockSize. > trying to brute force AuthenticationMethods publickey PasswordAuthentication no ChallengeResponseAuthentication no PermitRootLogin no
Just to double check my sshd settings I logged in to a server I have, and while it had "PasswordAuthentication no" set in the normal place in the config file, there was a line added to the very end of it "PasswordAuthentication yes", which I guess overrides the previous one. The server is reinstalling the OS right now...
Still, if you cannot explain how that second line got in there, it is probably prudent to reinstall (perhaps even reflash BIOS).