My bet is high altitude aircraft contrails. I think the reason you saw them as red rather than white is that they were illuminated by the setting sun, which happens later if you are at a significantly higher altitude.
It happens with high flying clouds too sometimes, when they are called 'noctilucent' clouds. I think what you've seen is noctilucent contrails. You can see a selection of them at https://www.flickr.com/photos/35423990@N00/sets/72157600329483616/ These are evidently older and have dissipated and been distorted by the wind. I imagine yours, if they were straight, were more recent.