is fail2ban safe? Better to use ssh keys?

I judge it as a stable product and I regard it as safe. As an extra precaution I would add your source IP address to the ignoreip directive in the jails.conf to make sure you don't block yourself.

Since it parses the ssh logs a TCP session is going to have to be established so spoofing source IPs and getting the TCP sequences numbers right to create a sort of backscatter variation seems unlikely.

Using keys on top of this as well isn't a bad idea. Other options that help are moving ssh to a nonstandard IP, using the "recent" iptables module, or just deciding you don't care if people try to brute force passwords. See this serverfault post for more on these.

Every time I've ever implemented denyhosts or fail2ban in a production environment it has created a guaranteed ticket-stream of unlock requests, password reset requests, requests to change the settings or manage the whitelist, and generally just people who give up logging in to look into things and lean more on the sysadmins for stuff they could do themselves.

Its not a technical problem with either tool per-se, but if your users number in the dozens or greater its going to be a noticable uptick in support workload and frustrated users.

Also, the problem they solve is they reduce your risk of brute force ssh login attacks. Honestly, the risk of that is incredibly small as long as you have even a moderately decent password policy.

I use since few years and at least is a good protection against script kiddies.
No root logon, plus pretty long and random passwords and fail2ban and maybe different port is for most of us enough secure.
Of course ssh keys are much better as security.

I've been using denyhosts in several of my production and non-production servers, and it works real fine (I had problems with daemon sync, so I don't use it now, but maybe it's working fine again).

Not only makes your system safer, but it helps you keep cleaner logs and simply keep out undesired people out of your login screens...

I've run Fail2Ban for a little while now, and just recently I've seen distributed attempts to break in to my SSH server. They'll never succeed at the rate their going, but I've been keeping an eye on it.

They've been going through a dictionary, each IP tries twice, after those attempts fail another IP does the same, etc. I've considered banning IPs that try unknown usernames x times. But so far I've gotten a few thousand different IPs trying to get in; and I'm concerned that even if I block them all there'll still be more.