Thanks! After hours of digging my best bet is that Sidekiq restarts when the server is under stress (IO, CPU, RAM), but I could not pinpoint more clearly (no logs, no OOM).
The frequency of restart since moved from once a minute to once every ~10 minutes (thus allowing the processing of the queue), then to even less.