Any of a kind Bitcoin wallet need to share private key on the internet-connected machine.

Bitcoin client has no responsibility for to keep private key secure. If your's machine connected to the internet, your keys can be hijacked, because your machine can be hacked before you import keys.

The questions is, how to trust any of existing crypto-wallets to store private keys?

P.S. My answer is "no trust" to all of them.