Almost all of the versions for tenor are in the key of Eb major for Bb instruments, with the bridge modulating to E major and then back to Eb major. This is also the case for Coltrane's version, which although he reharmonised the accompaniment he still ended up in Eb major, having modulated in the bridge to E major.
Eb major, key signature three flats - yes it has the same key signature as C minor, but it is definitely a major key.
E major, key signature four sharps, same key signature as C# minor but again a major key. The sheet music of the original version starts in C major, modulates to Db major for four bars, then E major/C# minor for four bars before returning to C major. Strange as it may seem, the jazz changes Chris provided and which just about everybody plays nowadays, are actually simpler than the original, with only one written key change in the bridge.
Having said all that, in the A section, think ii or V going to I (for tenor that is F-7/C7 going to Eb major) and you will be on track.
In the bridge you could think of it as four bars of E major going down to Dmajor for three bars then modulating in the last bar of the bridge to bring you back to F-7 and the key of Eb major.
Again, this is the theory, just play the head over and over to the backing track and your ear will tell you what to do.
All the best, Bill