Recently I had to setup a new laptop and forgot that the SSM feature of the AWS CLI requires an additional (and denoted optional) plugin to be installed. This SSM plugin plugin can be obtained here. It took my quite a while to find out that the missing plugin is the source of this rather obscure SSH client error message.
kex_exchange_identification: Connection closed by remote host Connection closed by UNKNOWN port 65535
Since there were some changes regarding supported ciphers and other versions of the involved tools, I was digging down the wrong holes. Installing the plugin fixed it.