Issue solved. The problem was, that we stepped through the code and because of that too much time elapsed between connect and authentication. As we ran the program without breakpoints it worked.
The AuthenticatePw method failed and the LastErrorText contained this information:
ChilkatLog: AuthenticatePw: DllDate: Jan 31 2010 UnlockPrefix: *** Username: *** Component: .NET 2.0 SshVersion: SSH-2.0-XFB.Gateway Windows SftpVersion: 0 login: *** sendMessage: msgName: SERVICE_REQUEST unpaddedLength: 22 remainder: 6 paddingLen: 10 totalSize: 32 SentServiceReq: ssh-userauth numBytesRequested: 16 Connection closed by server. Failed to read data on SSH connection. Failed to read packet from SSH server. Error reading service accept. Socket connection lost. Failed.