Wobbly splined cranks, yet bolts are very tight
Sounds like wear between cranks and bottom bracket.  Strange its the same on both sides, I'd expect your primary foot side to be more worn.

Have a good look at the interface between crank and BB.  Look for wear and witness marks to see if they're worn together or just the BB or just the cranks are worn.

You shouldn't have to change your chainrings unless they're a one-piece unit with the right-hand crank.