> Credit card numbers in our database are stored in encrypted format, using public and private key encryption. The private key is itself encrypted with passphrase encryption and the complex passphrase is not stored electronically.
By not providing further clarification that the private key was stored outside that compromised host in that update, you can read between the lines that they are trying hard not to address that particular issue.
I really don't want to assume that the attacker can now brute force the private key's passphrase, and it might not take long if that "complex" passphrase was a word out of /usr/share/dict/words.
Or worse, that the billing process was monitored via the compromised network, RAM, or a key logger - to get the unencrypted private key or it's passphrase.