OP mentioned the problem persists from BOTH CD and TT, sooo, that rules out source equipment.
It is unlikely both speakers would develop problem(s) at the same time. So, simply switching speaker wires, left to right, right to left, NO OTHER CHANGES: IF the problem moves to the other side, it's that speaker.
Tubes: get paper, make notes, easy to confuse yourself or forget. Swap all tubes L to R, problem move? Next: using tubes from the 'good side', swap l/r one at a time, any single tube swap make a difference?
Many tubes last 10,000 hours, so 5,000 hours is not a DEFINITE answer. Ask seller about the tubes you bought from him, what are the life expectancies of the tube types your unit uses?
...................................................
How many times have I advised a simple tube tester to give answers when problems occur????????????????????????? Blindly buying tubes is an expensive shot in the dark.