Deleting a certificate from the certificate user store, leaves the private key untouched, it is both insecure and creates unnecessary clutter.
Before deleting a certificate, first indentify the unique key id with:
certutil -store -user My [serialnumber]
* remove the "-user" for local machin store
Look for these lines:
Now, to delete the key use this:
csputil -csp [csp name] -delkey [key unique id]
If successfull, you man delete the key
This method is both valid for KSP (CNG) and CSP.