What is the remote device? If it is RouterOS does it have strong-crypto enabled too? If it is not ROS devices, does it have enabled all needed algorithms that is used by the ssh client when strong crypto is enabled?
I have tried to SSH to another mikrotik deivce that has strong crypto enabled. I have also tried to SSH to my Proxmox host running version 6 which has the up to date crypto and hash enabled. I get the same result no matter what I try and SSH to.