The 35 amps you were putting thru the 40 amp ssr is definitely to great, especially without a heat sink. 80% of maximum is normally a good target to shoot for. Here is a link to determining a proper heat sink size:
http://www.omega.com/temperature/Z/pdf/z119-121.pdf
Or do as JTW37 suggested and purchase an SSR and heatsink combination. I would recommend something larger than 40 amps based on your load.