Как реализовать авторизацию через api?
OAuth2.0 и обязательное использование защищённого соединения (SSL).
Или генерировать токен рандомно и хранить его в базе?
Именно.
У пользователя есть некий ключ, он им подписывает свои запросы.
Например ключ qwerty, в запросе передается user_id (например метод getUserNameById), тогда подпись - некая хеш-функция от параметров и ключа, например sha1($key . $methodName . $userId)