What I think is happening is that the trigger is making 5 or so SOQL queries for each batch of 200 records, and then it is running 25 sets of 200 to finish all of the 5000 records with 5 * 25 SOQL queries going over the limit.
Is this how limits work?
This sounds like a likely scenario to cause this exception if what you're doing is in fact inserting 5,000 records in a single transaction, and you can document that your code uses 5 SOQL queries per 200-record trigger invocation.
However, the SOQL limit is a transaction-wide limit. If your trigger invokes other classes or performs DML that fires other triggers, the SOQL consumed by those code elements is also counted against the transaction limit. (I'm eliding the complexities of certified managed packages here, which get their own set of limits).
how can I best change my trigger code to deal with large numbers of records being updated?
5,000 records in a transaction is a very large number of records. Sometimes it is simply not possible to tune code to use fewer than 5 SOQL queries on a 200-record trigger batch.
You should, as a general good practice, make sure you're not wasting SOQL where you don't need to be. You should cache results where you can, and use the Describe API instead of querying for record types, and so on. But fundamentally, 5 SOQL per 200 records is fairly efficient, and we cannot make more concrete recommendations without seeing your code.
You could look at refactoring your trigger to push as much functionality as possible into asynchronous operation, like a Queueable chain. That will certainly alleviate some of the limits issues you confront, but it's harder to test and doesn't run in real time.
This may be a long-winded way of saying "stop trying to insert 5,000 records in a transaction".