Steven,
If you replace both battery cables, be sure BOTH cables are at least 2 gauge. However, 1, 0 (1/0), or 00 (2/0) gauge cables are better but heavier. I use 2/0 (00) gauge cables.
If you cannot find heavier cables, try a welding supply shop and look for proper-sized copper lugs/ends.