Cost problem

Hello.

I use psql (PostgreSQL) 7.4.5.

I have a cost problem.

A simple select lasts too long.
I have a table with aprox 900 rows.
All rows are deleted and reinserted once a minute.

EXPLAIN SELECT * FROM logati;
QUERY PLAN
-------------------------------------------------------------------
Seq Scan on logati (cost=0.00..100741.22 rows=1198722 width=340)

EXPLAIN ANALYZE SELECT * FROM logati;
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------
Seq Scan on logati (cost=0.00..100741.22 rows=1198722 width=340)
(actual time=35927.945..35944.272 rows=842 loops=1)
Total runtime: 35945.840 ms
(2 rows)

Tha problem is that "EXPLAIN" function raports that the table has
1198722 rows.
But the table has only 836 rows and the select lasts a lot.

If I recreate the table the number of rows is ok and the select is quick
for some time, but it becomes slower in time.

How can I fix this?

PS: The table has a index but no primary key.

Thank you