Computer won't boot randomly, but always does if I flip the PSU switch

Hello, I've had a problem for a long time, with it going away and back and I think I need help now.

I'm literally afraid to turn off my computer because it won't turn on, and if I leave it on, it may randomly turn off with Kernel-Power 41 being in the log. I have switched almost all parts now except the motherboard and the CPU, but the problem persists.

What happens is:
The fans are behaving differently, I would guess they are supposed to slow down at once, but they won't so it's easy to hear if the PC will boot or not.
Monitor doesn't get a signal
Nothing happens until I hold the power button to turn it off or it just restarts randomly.

However I can boot it each time if I flip the on/off PSU switch really fast. The fans slow down, and everything goes ok, but I don't think it's a good idea to do it.

The PC also randomly shuts down, I've mostly seen it happen after long periods of being turned on.

I've made a clean start a few days ago after I got my SSD, but it's no good.

Would appreciate help.