It's probably not about 4096, but about rsa-sha2. Which is supported since 5.20:
Issue 1952 – Support rsa-sha2-256 and rsa-sha2-512 SSH public key algorithms

Hi,

I'm trying to use WinSCP.exe 5.17.5.10414 to connect to a SFTP server with a ssh-rsa 4096 host key but I get the following message:

Couldn't agree a host key algorithm (available: rsa-sha2-256,rsa-sha2-512).

With the most recent version of WinSCP.exe (6.5.1.16311) I can connect flawlessly.
I suppose that 4096 key support has been introduced in later versions > 5.17.5 but I can't find nothing about it in the public changelog.
I know I'm using a pretty old version, but is it supposed to work on my version or updating WinSCP is mandatory? What do I have to do to make it work (even a solution that involves WinSCP .NET API could be ok for me)?

Thank you very much
Ivan