We have an AppExchange App which needs to connect with an external application via API Calls. API calls need to happen in individual user context and not in a single Integration User context.
This means to use the External API, every user has to authenticate once to the external application and their Access Token/Refresh Token will be stored in the protected custom settings.
Salesforce custom settings has a storage limit as mentioned in below URL:
For example, if your org has three full licenses, you have 3 MB of custom setting storage. If your org has 20 full licenses, you have 10 MB of storage.
Each certified managed package gets a separate limit in addition to your org limit. For example, let’s say your org has two certified managed packages installed and your organization has three full licenses. Each certified managed package can have 3 MB of custom setting storage in addition to your org’s 3-MB custom setting storage limit.
With the above limitation, using a Protected Custom Setting for an org with a large number of users will be an issue. Based on the calculation shown in the below link, a custom setting's record size is 610 with 2 Text (255) fields. Which will hit the 3MB limit if the number of users exceeds 5156. https://help.salesforce.com/articleView?id=000318587&type=1&mode=1
Question: Is there any alternate to Custom Protected Settings while storing the sensitive information in the AppExchange product for a large number of users? Also, the storage limit for an Org is the hard limit or it can be increased with some add-on after contacting Salesforce?