It’s possible that they discovered a weakness in the way the keys are generated in the TPM (or whatever it’s called for Android), which brings the time to brute force down from 1,000 years to a few weeks with massive GPUs?

Similar story, as of a few years ago, OpenSSH announced deprecating support for RSA keys keys because of a vulnerability in SHA-1 hashing, where they cited research showing a determined attacker could break the key with $50k of compute power, which may seem like a lot, but is pretty feasible, necessitating the deprecation

It is now possible [1] to perform chosen-prefix attacks against the SHA-1 hash algorithm for less than USD $50K. For this reason, we will be disabling the “ssh-rsa” public key signature algorithm that depends on SHA-1 by default in a near-future release.

I don’t know about the Android system, but during the initial design and fabrication, the hardware may have not been designed to withstand the compute power just a few years later, and can not be easily updated to improve the security. These are the weaknessed Cellebrite is looking for.