Efficient Feasibility Checking of SBBD Matrices

I have a collection of singly-bordered-block-diagonal matrices. That is, each SBBD matrix looks like:
H = [H_0                 ... C_0;
                H_1         ... C_1;
                       H_2  ... C_2;
       ....                                ]
The number of blocks is constant for my collection. On the order of ~10 blocks. Another very relevant note: the collection arises from letting each pair (H_i, C_i) vary over some finite set of options. I want to consider all variations/combinations of variations.

For each SBBD matrix, H, I'd like to solve the feasibility problem Hx>0 for x a real vector. This is trivial to do using standard LP methods, but such methods are too slow (~0.1s per problem) for my context. Specifically, a given collection of problems might have size ~10^6 different problems. (In the worst case, it is of order 10^400, but I'm not bold/naive enough to expect to be able to solve 10^400 problems...)

I believe a good strategy is to use Bender's decomposition, for which I treat the block-diagonal part of H as the 'master problem', and the band as the 'subproblem'. By framing it in this context, I hope to be able to frontload some work (solving H_i x>0 for each i), and use that as a good starting point for each problem in my collection.

My questions:
1) is the proposed approach a good one, or should I pursue a different approach?
2) how might I implement this in GurobiPy? I know there are some posts (https://support.gurobi.com/hc/en-us/community/posts/13653393586961-Benders-decomposition-example-in-Python, https://support.gurobi.com/hc/en-us/community/posts/4415191730321-Benders-Decomposition-using-Callback, and https://support.gurobi.com/hc/en-us/community/posts/6482463141393-Benders-decomposition-in-Gurobi) discussing this, but they don't seem very relevant to my work.

This area is not my expertise, so I apologize if this question is confusing.

I would really love it if I could perform a (potentially large) upfront cost so that I can solve such problems at scale.