Yes, I would most definitely step up to 4 gauge...and as for the fuse, remember, it isnt there to protect the amp (though it is a good idea to make the ratings come close to the amps max current draw)...its there incase your power cable grounds itself and short-circuits, the amp should have its own protection...be it fuses or circuitry inside to go into protect-mode.
But yes..
-A new, good battery (such as XS Power, Kinetik, Stinger, BatCap, Yellow Top, Northstar, Odyssey etc.)
-4 gauge all around (including upgrading the Big-3 under the hood to atleast 4-gauge...I would use 1/0 gauge)
-60 amp fuse should do fine
-Make sure to find a good ground as well that is scrapped clear of paint and dirt and cleaned before making the connection
That right there should solve it, and it is pretty easy to do and not ridiculously expensive or anything.
PS-I would just try upgrading your wiring and do the Big-3 before the battery because I bet that may be enough to help the situation..and head to knukonceptz.com and check out their power wire...very reasonable prices for good power wire (try the klmx...good wire and great price)