Replacing OEM Android is only one part of the equation. There are many components that run with full privileges (EL2/EL3?) outside of Android and never subject to Android's sandbox. Well, at least until Google can force OEMs to stricter standards with their effort to KVMize those privileged executables [0].
If you do not trust the OEM, replacing its ROM with GrapheneOS / CalyxOS / LineageOS isn't going to help much anyway.
One right answer to this is fully open-source (hardware and software) phones like the PINE64 and Librem, among others.