While Israel may be restricted from Middle Eastern Arab countries, North Africa is a bit different. The EASA has a list of countries they have a working agreement with, which includes both Israel and Tunisia
As part of the process of creating a wider Common Aviation Area with its eastern and southern neighbours, the EU negotiated a comprehensive Euro-Mediterranean agreement with Tunisia which has been initialled on 11 December 2017. This comprehensive agreement will result in an increase in the number of direct flights and boost trade and tourist flows between the EU and Tunisia. Beyond market opening, the agreement also provides a modern framework and high standards for a wide range of aviation issues, such as safety, security, passenger rights, air traffic management, economic regulation, competition issues or social aspects.
As to Algeria (not in the EASA), the answer is probably more mundane: airspace fees
Many countries use airspace fees as a form of revenue and, sometimes, as a form of leverage during political negotiations. This causes prices and routes to fluctuate, with airlines subject to different policies. Costs are, of course, transferred to travellers, while airspace restrictions can significantly limit the options available to certain destinations.
Algeria uses France's ENNA to collect their fees
Overflying navigation fees are generally imposed by the country’s civil aviation authority (CAA) although some countries have other entities responsible for their issuance, such as the airport authority, or specialist local government bureaux. In Algeria for example, responsibility lies with ENNA, the National Enterprise for Air Navigation.
As such, Algeria doesn't want in Israelis in their country, but probably doesn't mind their money to fly over nearly as much.