Il modo più efficiente sarebbe confrontare il tuo timestamp (e solo il timestamp, senza utilizzare alcuna funzione su di esso) con un'espressione che può essere calcolata come costante per ogni riga, in questo modo mysql può utilizzare l'indice definito sulla colonna del timestamp.
SELECT * FROM myTable
WHERE last_seen >= NOW() - INTERVAL 10 MINUTE
Puoi sempre provare EXPLAIN SELECT ...
per vedere se un indice può essere utilizzato per trovare righe che soddisfano la tua condizione WHERE senza la necessità di controllare ogni riga della tabella.