This seems not an unreasonable direction. You will end up (assuming you don't replace the config files) with config files with references to /etc/ssh-nonfree for the host keys. I'm also not sure that you want to depend on ssh-krb5 in preference to ssh. I realize that ssh-nonfree currently builds against Kerberos. Do you think that more people have it installed because of this, or because they never upgraded from ssh-nonfree to ssh?