There are much better linear regulators than the 7805 these days (with low drop-out-voltage particularly, the 7805 needs about 2V above the output).
Switchmode regulators save power but can produce a lot of noise (this may affect the analogRead() values).
You can probably find a directly pin-for-pin compatible replacement linear regulator. I can't remember what regulator the Mega uses (mine is inside a metal box on one of my projects, hard to get to!).