Daily Login Limit
The limit is specifically on calls to login() via the SOAP API, which is what your application is currently doing with the security token. Since the limit is 3600/hour, it appears that your application is performing a new login once per second.
You can probably fix this problem just by holding the session id during its validity period, as recommended in the knowledge article Sign in error 'Login Rate Exceeded':
Make sure that you are reusing the session, and not making a login call for every API request
That said, there are a wide variety of good reasons to switch to OAuth authentication, including that your application does not need to store actual credentials, which is a poor security practice. While you'll have to pay attention to other platform limits in any case, such as the total API call limit, any OAuth flow that involves storing an access token and a refresh token should both increase your security and get rid of this error.
Edit
Let's be clear here. You've now stated that the login limit is not your issue, but the daily API call limit is.
Using OAuth authentication means, per the question that you linked, that the calls you make to authenticate to Salesforce do not count towards your API limit. Regular calls made to the Salesforce REST API after authentication always count towards your limit, and there is no magic trick to make them not count.
If you are exceeding the Daily API Call limit, you need to either
- Work with your account executive to request an increase in this limit.
- Optimize your remote application to make fewer calls, such as by using the sObject Collection and sObject Composite resources. However, only your developers can testify to what exactly your app is doing to burn 1 million API calls and how then to fix it.