Relay and current

Measuring the actual current drawn by those lights would be the first step. The fuse is a CYA thing. It may be overrated by a factor of two or more. Look at the wiring. Does it look like it can handle even one amp?