After playing with this a bit more I've found the minimum necessary additions to the sshd_config for allowing TelnetPro to login for systems that have disabled sha1 by default, the minimum requirement is to have diffie-hellman-group1-sha1 like this:
KexAlgorithms diffie-hellman-group1-sha1
Though you will likely have more like this:
KexAlgorithms diffie-hellman-group1-sha1,diffie-hellman-group14-sha256,diffie-hellman-group16-sha512,diffie-hellman-group18-sha512,ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,curve25519-sha256
and for Ciphers, aes192-cbc needs to be added to the default list. On my machine this results in the following line for Ciphers:
Ciphers chacha20-poly1305@openssh.com,aes128-ctr,aes192-ctr,aes256-ctr,aes128-gcm@openssh.com,aes256-gcm@openssh.com,aes192-cbc
You can find out what your current ssh servers defaults are by using nmap on a machine that has it. (search for Ciphers in the output):
nmap --script ssh2-enum-algos -sV -p 22 localhost
Would work if you have nmap on the server that's running ssh and ssh uses port 22 and listens on localhost. Change to work with your specific setup.
Note that this doesn't seem to work for sshd 7.3. That would require a change in TelnetPro.
Edit: updated the KexAlgorithms line.