First, make a full backup of your environment. The easiest way to backup Certificate Manager is to take a copy of the RSA_CM folder.

In the steps below, the term OldCA refers to the CA you want to roll-over the key (your actual CA before roll-over)

Access RSA Certificate Manager Administration console
Click on CA Operations
From the drop-down list of CAs, select the OldCA
Note the entire Subject DN, this will be needed in the next steps.
Under Local CA, click Create
From the Issuer drop-down, select Self
From the Jurisdiction drop-down, select Copy of the OldCA
Click Next
Enter a nickname different than your actual CA
Enter the exact same Subject DN as the OldCA (Subject DN noted in step above)
Set your new validity dates
Set your new signing algorithm (if you have hardware based keys, select the proper option)
Select a profile extension if needed
Click Next
If using an HSM, select the proper OCS and click Next and enter the OCS PIN
Click on Create CA
Upon CA creation, restart the Secure Directory service
Close your browser
Access RSA Certificate Manager Administration console
Click on CA Operations
From the drop-down list of CAs, select the OldCA
Click on Generate PKCS#10
If this CA key is hardware based, provide the OCS and PIN
Click on Download PKCS#10 as PEM, save it as "oldCAKey.p10"
From the drop-down list of CAs, select the newly created CA
Click on Generate PKCS#10
If this CA key is hardware based, provide the OCS and PIN
Click on Download PKCS#10 as PEM, save it as "newCAKey.p10"
Open a new browser (keep your existing one open) and access the enrollment server
Select the Jurisdiction of the OldCA, click Continue
Click on "Make a PKCS #10 Cross-Certificate Request"
Click Browse and select newCAKey.p10 and click Submit
Go back to the enrollment server home page
Select the Jurisdiction of the newly created CA, click on Continue
Click on "Make a PKCS #10 Cross-Certificate Request"
Click Browse and select oldCAKey.p10 and click Submit
From the previous browser, still from the Administration console
Click on CA Operations
From the drop-down list of CAs, select the OldCA
Click on the Cross-Certificate link in the left side menu
Click on the request link
For Certificate Name, enter "New CA signed with old key"
Change the Valid Until to the expiration date of the oldCA
If you need specific extension in your rollover certificate, select the extension "Custom CA".
From "PKCS10 Extension" column, select
    Subject Key Identifier
From the "Available extension column", select
    Authority key Indentifier
Click issue
This is your NewWithOld certificate. Click on View and save the content as a .cer.
From the drop-down list of CAs, select the newly created CA
Click on the Cross-Certificate link in the left side menu
Click on the request link
For Certificate Name, enter "Old CA signed with new key"
Change the Valid Until to the expiration date of the oldCA
If you need specific extension in your rollover certificate, select the extension "Custom CA".
From "PKCS10 Extension" column, select
    Subject Key Identifier
From the "Available extension column", select
    Authority key Indentifier
Click issue
This is your OldWithNew certificate. Click on View and save the content as a .cer.