You can try ice cubes made of soda for having only soda. You can try having spherical cubes instead of small cubical ones, which take more time to melt.
Or else try adding some salt to the water and freezing it. It reduces the freezing temperature of ice which makes the ice freeze faster and melt slower.(But 10 gm of salt in 10 litres make a change of 0.1 Celsius change)
You can also try with different shapes of trays which you use, a tray with less surface area, the less surface area exposed, the less it will melt.
Ice made in plastic trays and silicone molds freezes from all sides, trapping impurities and making for a weaker cube. Using an open insulated cooler, which forces a top-down freeze, making a dense, slow-melting ice.