The host key we are using was supplied by the customer. It is way over 16 characters and does not have any colons.
Does it start "ssh-rsa 5561", i.e. does it match the key shown by WinSCP (despite a different syntax)?
If it does, just use the format that WinSCP shows.