I am attempting to come up with a reasonable way of implementing a design that was intended for cheap computer applications in the 1980s and which was originally designed to use a pair of TTL PROMs (a 28S42 and a 24S10) to control a state machine and decode state to outputs. The usual recommendation I see for these devices (which are still available, but at ludicrously high price -- the cheapest I see from a distributor is in excess of £30 per chip) is to replace them with a parallel EPROM, but the fastest EPROM I can find has 45ns access time which is cutting it very fine for the 50ns cycle time I'm working to. I'd really like to find a replacement part that can match the 35ns access time of the original parts.
What kind of options do I have available? I've considered switching to an FPGA, but (1) this is a much more expensive solution than I'd ideally like and (2) FPGAs seem to only be available in surface-mount packages with narrow pin spacing, and I'm not really comfortable soldering those. I've looked at CPLDs, but I can't really tell whether they are suitable for this application: how would I encode the transition table of the state machine, for example? Are there parallel EPROMs or a similar technology out there that can match the access times of these old PROMs? Are there other possible solutions to this kind of problem that I'm missing?