Your GPU temperature definitely isn't normal for that card, does it have a fan and if so is it working?
I suspect it's either badly clogged with dust or that the heatsink isn't attached properly, those temperatures could certainly be causing this issue.
That aside, what make and model of PSU did you buy? Bad PSUs are also a common cause of random reboots.