Oracle: Physically reorganizing rows of a huge table by a different key
Create an index on (record_key, record_id). This way oracle will most likely use the index only to answer your slow running query. You can add more columns to that index, so that you also get the needed content. Hopefully you don't need all columns.

Be careful about, what impact this index has on your load performance.