Your phone's internal storage is divided into several different partitions. Almost all of them are dedicated to the installed Android operating system, with one set aside as a user data partition. The system-level partitions are protected and restricted, the user data partition is less restricted with just user-level permissions. That's a significant issue:
-- When you install something like the Malwarebytes app or some A/V app from the Play Store, that utility is installed with user-level permissions. It has complete access to all the content in the user's partition, but no or very, very limited access to any directories with system-level permissions.
-- A Factory Reset only wipes the user data partition clean, it does nothing to the installed operating system. So an non-rooted or a rooted phone running 12 will be the same before a Factory Reset as after. The only difference will be all the user data in that one partition is gone.
-- Flashing the firmware will reload a clean Android ROM, replacing the previous install. If something like an actual rootkit did compromise the installed OS, flashing the ROM will over-write it.
So if you did flash a proper ROM and that rootkit is still there, there's not much more you can do. You can keep trying to manually remove it, but a more prudent measure might be to just start looking for a replacement phone.
How are you determining your phone is actually infected with a rootkit?
Is your phone rooted or still stock? Which leads to the question did you use a stock ROM, or a third-party ROM (i..e. LineageOS), or a backup image you created yourself?