I was having a similar issue with my Power Color Demon RX 6900 XT.
I was running an EVGA 850 watt PSU (Recommended). Then I upgraded to a Thermaltake ToughPower 1200 watt and the problem went away.
I would suggest a minimum of a 750 watt PSU but I would recommend a 900 watt PSU so you have plenty of overclocking headroom. Plus PSU's are one of the few PC components that didn't skyrocket in price. Checkout Newegg.com they're great for comparison shopping PC parts.