La forma más eficiente sería comparar su marca de tiempo (y solo la marca de tiempo, sin usar ninguna función) con una expresión que se pueda calcular como constante para cada fila, de esta manera mysql puede usar el índice definido en su columna de marca de tiempo.
SELECT * FROM myTable
WHERE last_seen >= NOW() - INTERVAL 10 MINUTE
Siempre puedes probar EXPLAIN SELECT ... para ver si se puede usar un índice para encontrar filas que satisfagan su condición WHERE sin la necesidad de verificar cada fila en la tabla.
