I think this may have to do with using the Windows temp directory. When I changed it to c:\mywinscptemp connecting suddenly became instantaneous.
Perhaps it is searching the whole Windows temp directory? Mine contains hundreds/thousands of files.
Anyway you may be able to give WinSCP users faster connection times by using your own temp directory, or a subdirectory of the Windows temp directory.