Las claves privada y pública del certificado deben tener el mismo algoritmo, ¿correcto?
Sí, por supuesto, pub / priv son un par de claves.
Entonces, este código sería legal, para ser más flexible (por ejemplo, ECDSA o DSA):
PrivateKey privkey = (PrivateKey) keystore.getKey(keyAlias, passphrase);
Certificate cert = keystore.getCertificate(keyAlias);
KeyFactory keyFactory = KeyFactory.getInstance(privkey.getAlgorithm()); //before: "RSA"
publicKey = keyFactory.generatePublic(keySpec1);'