SSH Sometimes works, sometime doesn't - local network

Does this 'server' have a public facing SSH port?

You could be results of someone trying to brute force logins to your server if you have the default MaxStartups settings the server will only allow a limited number of incoming connection attempts at any given point in time, and will reject the rest.

The logs you would see in this case would be tons of authentication failures in /var/log/auth.log.

You could also be getting rejected from some other intrusion prevention system perhaps implemented with netfilter or something else.

Assuming this is a result of the MaxStartups or some other intrusion prevention system, you should generally not make SSH public facing, or if it is public facing limit the incoming addresses to trusted subset or require a VPN or something.

Putting ssh on a non-standard port can help cut down probing and brute forcing from the internet.

In case this is helping you, I had a similar problems.

AFter ruling out fail2ban and sshd_config I found out that I used ufw with a LIMIT rule to the ssh port. I blanky allowed SSH and now it works. Issue was with too many connections.