Linear regulators overheating
This is a great example of why you need to do the math and nost just blindly build something.  It should have been obvious from the start your regulators would get hot just from the basic physics.

You say you have about 18 V in and that each regulator is producing 12 V at 1 A.  That means (18 V - 12 V) * 1 A = 6 W is being dissipated by each regulator.  That is way more than a TO-220 case can handle in free air.

There are two obvious options:

Put a heatsink on each regulator.  Make sure it can handle the 6 W of power and still keep the part cool enough at whatever your ambient temperature is.  This time do the math up front.  Make sure to take into account not just the thermal resistance of the heat sink but also the thermal resistance of the die to the case.  The total must be low enough so that 6 W into the die won't exceed its operating temperature.

For example, let's say you need to keep the die at 125&deg;C or below (I just made that up, it's your job to look at the datasheet and find the real number) and that your ambient won't exceed 25&deg;C.  That means you can afford up to 100&deg;C rise in the die above ambient.  Since 6 W of power is being dissipated, that means your combined die to case and case to ambient thermal resistance needs to be 100&deg;C / 6 W = 16.6&deg;C/W.

Use a swithing regulator.  At these voltages, you should be able to find something that can do 2 A out.  The single switcher will replace the two linear regulators.  It will also be smaller and cheaper since it won't have to deal with getting rid of 18 W of heat.