I'm assuming you received a much longer error messages than just "Host key verification failed". Generally this error relates to the remote host key saved in your .ssh/known_hosts file not matching the /etc/ssh_host_*_key. The longer error would mention known_hosts, and specify which line number it thought was not matching.
If I am correct, then I think you have 3 options.
a) Edit your .ssh/known_hosts file and remove the offending line.
b) Delete the known_hosts file and allow it to be repopulated.
c) Add the following to your ssh command line
ssh -o StrictHostKeyChecking=no ...
The -o StrictHostKeyChecking=no assumes you trust that noone will attempt a man in the middle attack, or that someone will try to impersonate your remote system.
I am wondering about the use of both -t and -T on your ssh command. Force tty allocation and disable tty allocation. Seem to be a conflicting desire to me. When I try this, I get "sudo: no tty present and no askpass program specified".
Also unless the remote system's /etc/sudoers file does not require authentication for what you are trying to do, how are you going to enter the remote admin password if you do not have a tty connection to the remote? Just wondering.
If you still have problems, you might try getting more ssh diagnostic information using
ssh -v -v -v ...
and if you have any system where your ssh command works, you repeat the ssh -v -v -v to that system, and then compare the diagnostic output to see what is different, and often times it is the differences that tell you what went wrong.
