The article is rather misleading. It is almost certain that Samsung used HSMs to sign their APKs, so the key itself could never actually leak unless someone had physical access to the HSMs themselves and managed to somehow delid it and then put it back together without anyone noticing. I'm not too familiar with the documented attacks on delidding HSMs, but I believe that delidding chips causes permanent damage to them in such a way that they will never function properly again.

It's much more likely that an employee's account was compromised and then used to sign malicious APKs, or something similar. Once Samsung realized, they could get the logs of every APK signed with the HSM and then revoke those certificates individually through a software update. Not really sure if they actually did that or not, but either way the key doesn't necessarily need to be replaced.