I agree with the rest, a switching solution will almost certainly be smaller and more efficient.
But if you do want to continue with the linear approach, I'd suggest designing for 5V output to start with. Choose a transformer with a 6V secondary instead of 12V. Most of the heat and inefficiency comes from the size of the voltage drop, so if your unregulated DC starts out close to the target, you will generate way less heat. Of course, with your current requirements, that transformer needs physical space. I'm thinking about a 3-inch cube.