Unable to push to device from Panorama due to the following error: "cannot find complete certificate chain for certificate, failed to load: failed to parse key"

While performing a configuration migration between Palo Alto Networks Firewalls, push to device from Panorama may fail with the following error: 

Log Analysis:
Warning: No Valid DNS Security License
vsys1
Warning: cannot find complete certificate chain for certificate 'generic certificate'
Error: Certificate 'generic certificate' failed to load: failed to parse key
Error loading vsys cfg
failed to handle CONFIG_UPDATE_START
(Module: device)
client device phase 1 failure
Commit failed

• Palo Alto Firewall migration from PA-220 to PA-460
• PAN-OS 10.1.3
• Firewall being managed by Panorama.

1. Validate the commit errors on Panorama to identify the certificate that is being pushed to the Firewall.
2. On Panorama, Go to Templates > Device > Certificate Management > Certificates to find the certificate being pushed.
3. Redeploy a new certificate with a new private key. 
4. Make sure to apply this new certificate on the same references and policies as the old one, otherwise, other errors will follow.