Full Table Scan - as the DPA Advice says, probably first thing to look at is whether there are any suitable indexes? If so, are the table and index statistics up to date?
If not, can you add a new index or modify an existing index?
Can the SQL be re-written to be more efficient?
Have you checked the execution plan?
It doesn't seem to be bringing lots of data back, so the inefficiency of scanning the entire table to return 1-2 rows per execution is going to be costly (even though it averages about 0.4 seconds per execution).