You might get someone that recommends renumbering your table, don't do that.
I would do something like this (but there are probably more ways to do it) ...
The links on your page ...
In each page, if the variable "action" exists, that means that they clicked "prev" or "next".
If there is no "action" variable, then they want to display the page specified, so it works as normal.
If they assigned a value to "action", then query it one way for "prev" and another for "next"
Previous ID ...
SELECT * FROM tablename WHERE id < $page ORDER BY id DESC LIMIT 1
Next ID ...
SELECT * FROM tablename WHERE id > $page ORDER BY id ASC LIMIT 1
The query will result in only one row ... which will be the one before or after
the specified page (id) ... depending on "action".