You apparently have a little under half your RAM available so if you're convinced use of flash is slowing you down, why not try a version with all (or some of) the F macro usage removed.
Don't forget that some of the the "free" RAM is going to be used by your variables though.
Also, your use of Strings will become increasingly risky, the less free RAM is available for the heap.