Create a secure private network between Linodes?

You could do this by assigning private addresses from our datacenter to each Linode and telling their respective firewalls to only accept connections from the IP addresses assigned to those Linodes. You can then remove the public IP addresses for each of the Linodes that should not be accessible to the public from their respective interfaces, leaving only their private addresses. It is also worth noting that in order to allow communication on our private network, you will need to keep all of the Linodes in the same datacenter. For example, if you have 2 Linodes in the same datacenter with the private addresses 192.168.1.2 and 192.168.3.4, your rules would look similar to this:

On 192.168.1.2, add these rules, remembering to substitute the example IP addresses for the addresses that you are actually using:

# default iptables policy - this ruleset will be followed for
# connections that have no associated rule
iptables --policy INPUT DROP
iptables --policy OUTPUT ACCEPT
iptables --policy FORWARD DROP

# allow all communication to and from 192.168.3.4
iptables -A INPUT -s 192.168.3.4 -j ACCEPT
iptables -A OUTPUT -d 192.168.3.4 -j ACCEPT
# similar rules for other servers living
# in the private network go here

# On 192.168.3.4, add these rules, remembering
# to substitute the example IP addresses for
# the addresses that you are actually using:

# default iptables policy - this ruleset will be followed for
# connections that have no associated rule
iptables --policy INPUT DROP
iptables --policy OUTPUT ACCEPT
iptables --policy FORWARD DROP

# allow all communication to and from 192.168.1.2
iptables -A INPUT -s 192.168.1.2 -j ACCEPT
iptables -A OUTPUT -d 192.168.1.2 -j ACCEPT
# similar rules for other servers living
# in the private network go here

If you wish to have more granular control (e.g. if you only wish to allow communication on a specific port), you can use a ruleset like this:

# default iptables policy - this ruleset will be followed for
# connections that have no associated rule
iptables --policy INPUT DROP
iptables --policy OUTPUT ACCEPT
iptables --policy FORWARD DROP

# this rule allows communication between 192.168.1.2 and 192.168.3.4, but only on port 22 (SSH)
iptables -p tcp -A INPUT -s 192.168.1.2 --sport 22 -m state --state NEW,ESTABLISHED -j ACCEPT
iptables -p tcp -A OUTPUT -d 192.168.1.2 --dport 22 -m state --state ESTABLISHED -j ACCEPT
# similar rules for other servers living
# in the private network go here

Be aware that the ruleset above will allow incoming SSH connections, as well as allowing the SSH connection to return information once a connection has been established, but it will not allow a user to run SSH from within the server on which the rule is configured. To allow that, you could alter the second rule to say --state NEW,ESTABLISHED. The NEW designation on the outgoing rule is what allows you to start an SSH session from that server to another.

I believe that this will ultimately be the simplest way, but make sure to account for all 7 of your servers when defining your iptables rulesets. Since I can't guarantee that all of the private IPs assigned by our network will be in the same subnet (they are randomly assigned by our system at the time that they are added), it would probably be best to configure rules for each IP, as opposed to configuring rules for an entire range, since this would allow communication from other Linodes in the same datacenter if they are in that range.

*** EDITED IN ORIGINAL ANSWER ***
I'd like to make a slight edit to this - a VPN would not necessarily require users to have the client installed. Since it has a public facing IP address and the server itself is hooked into the VPN, the end result should be a publicly accessible front-end which has access to the VPN, thus eliminating the need for users to install the client software. In light of that fact, either solution would probably be more or less equally effective.