Not to be insulting, but double check that "Remote Login" is checked on the Mac you want to connect to.
Also verify the username you are using to connect to the other Mac has permission to login over ssh.
You never know if somehow one of these items has changed somehow. It is also possible the preference file is corrupt so you can try to delete the Sharing .plist file and recreate it from scratch or restore it from a backup made before this issue began.
Are you using any anti-virus apps, cleaning apps, or third party security software that may be interfering?
Did you manually modify the ssh configuration file on the remote Mac you are attempting to connect to?
Have you tried putting one or both Macs into Safe Mode to see if the issue persists?