Changing the public key in an MD5 certificate
Given an existing certificate, it isn’t practical.

MD5 is preimage-resistant, so it is not practical (given $x, y: x = \text{MD5}(y)$) to find $z: z \neq y \land \text{MD5}(z) = x$

But MD5 is still a TERRIBLE choice

MD5 allows for trivial collisions.  This has been used by malware to forge code-signing certificates.