Just put a DC-DC converter between the car's (nominal) 12V net and the Mega and all of its sensors. Power the Mega with 5V from the DC-Dc converter by applying it to the Mega's 5V pin.
I don't see the need for a relay for the sensors. If you must use one, why not just use a PMOS high side switch instead?