I agree that Frost is the dependable way to go, but I think it sacrifices speed. Except that the better control might save you time from corpse-runs.

Arcane might not be a bad choice for fast leveling, though I've never used it myself. You couldn't really use Missile Barrage (+5% dps?), but I don't know what else you'd miss.

1. Mages have lots of insta-casts. Drive-by straggler killings should be no problem- that's fast. (Note the fire talents Incineration and Improved Fire Blast).
2. Arcane Explosion, with Arcane Subtlety, can be used for genuine AoE as long as your paladin is covering it with Consecrate- that's fast too. Just don't pull too many or the paladin might die. (Note the fire talent World in Flames.)
3. Arcane Missiles can be used to kill elites- otherwise it's too slow. A 5 second cast and lots of drinking on account of the mana. But it's got decent DPS, so for elites- that's fast.