Voltage regulator getting extremely hot
Check your heat sink - it should have a thermal resistance value in degrees Celsius per watt.  You have a voltage drop of 24-4.85 = 19.15 volts.  At 95 mA, you are dissipating 0.095 x 19.15 or 1.8 watts.  Your part has a thermal resistance of 50 degrees C/W, so the temperature rise would be 90 degrees C above ambient room temperature, or about 115 C (definitely too hot to touch!).  A typical TO-220 heat sink is around 24 degrees C/W, which would reduce the temperature rise to 45 C, so the heat sink temperature would be around 70 C.

The thermal resistance junction-to-case is 5 degrees C/W for your part, so at 1.8 W the junction temperature is 9 degrees higher than your heat sink temperature.  The part is rated at 150 degrees operating, so it should work, but you will be depleting your battery much faster than if you used a switcher as @Eugenesh suggests.

If you try to run at 35 volts and 2 amps, your voltage drop is 30.15 volts so you would be dissipating 60W.  Since the junction-to-case thermal resistance is 5 degrees per watt, the junction would have to rise by 300 Celsius even if the heat sink was maintained at room temperature.  So although the part may be good to 2 amps in one application with a small voltage drop, and may also operate at 35 volts in another application with low current, these can not occur together.