You know the melody so internalise it learn it in every key. As much as you want to play the changes never ignore the melody. You could play 4 rhythm changes back to back and what separates them is the head so it' always nice to be able to draw from that well at any given moment. Improvise with the melody and break down specific cells or building blocks of the melody and improvise with them. One of the amazing things about hearing Sonny Rollins improvise is that he spends so long learning literally no stone unturned and is like a dog with a bone. The more you dig into a single aspect the more creative you find you have to be.
You've identified the ii V progressions so isolate them and get that language together. Fortunately there is a wealth of material you can draw on since that language is ingrained into the jazz vocabulary. Your job is to find what you like, transcribe the ideas and take concepts and see what you can come up with. I'm always more interested in the concept rather than the specific line when I'm lifting stuff.
Your chord tones, for me personally, are the fundamentals. Know them and the permutations inside out because in order to play the changes you have to know whats happening on a chord. I'm not so big on the chord/scale theory as an approach to improvisation personally. Knowing the chord tones cold means you are able to resolve ideas and move from change to change. You can play an endless bunch of chromatics and sound like a musician falling down the stairs but you need to know whats going on each chord so you can highlight that. Once you've got the chord tones down then work on approaching them from below, above, above and below, two semitones below, two semitones above etc etc etc this is now moving firmly into the language that you are used to hearing.
Take one or two chords at a time and just run them to death. There is no harm in spending hours and hours on two changes and just hammering away at them until you are comfortable with them. Work through the tune that way.
After that you can play arpeggios of the changes going round the form. On the first chorus you can work on improvising over bars 1 - 4 and arpeggiating the changes for the rest of the tune. Once you are comfortable with that improve only on bars 2 - 5 and arpeggiate every other bar. etc etc etc. This will really help you dig into being able to start and end ideas at any point in the form which is a really important element of the music.
You'll hate me for this but learn to sing through the changes and the chord tones etc. This really cements the sounds into your ears and helps your play and translate the ideas you are hearing into your head on your instrument rather than just running your hands over the instrument because you know where notes are. Which is a very easy habit you can fall into on fretted instruments.
And transcribe, transcribe and transcribe!
Oh and transcribe.