Are the systems that work older systems? They recently
changed sshd to disable a lot of older encryption
and hash algorithms and wot-not. Perhaps it doesn't
like your old keys?
no because I regenerated the key and got the same result.
I wonder if the users need to be part of a group to be able to connect by ssh?
Frédéric