Protoboard components being used for applications with high current
If you are using one of those white plastic protoboards that has various series of holes that are bussed together 6 or 10 at a time then I would accomodate the relay as follows. 

Place the relay with pins facing up and solder on short wires to the low current pins that want to go into the protoboard. For the high current contact pins wire with heavier wire as appropriate (for 5A you may consider 16 to 20 AWG wire) that connect off to your load. I've tried to depict this in the picture below.