Problem
If you have a newly installed Link and you want to upload a certificate on a partner for the first time, you may meeting this message:
No private key has been set for the partner-certificates. Use the EdiPortal Administration Tool to generate a private key and save it in the EdiPortal Configuration.

Solution
Generate private key
Start Link Administration and go to BizTalk Settings.

Comment: The menu name 'BizTalk Settings' is a misleading name. It should Link Settings, because the settings is also about Link settings and not only about Biztalk.
Set the Key PartnerCertificatePrivateKey
You can read about PartnerCertificatePrivateKey here:
Link Settings
Look for PartnerCertificatePrivateKey in the Key column. I you don't find PartnerCertificatePrivateKey, insert it at the bottom.
Put in the generated private key under the correct environment:

Recycle app pool
