Why not use a perl style foreach loop:

foreach my $host_num ( 0..num_hosts()-1 ) {
    print "[$host_num] ", hostname_by_num($host_num), "\n" ;
}
[download]

Better yet why not change the lookup function to index from 1 and prevent accidentally mucking about with HOSTS.

use Scalar::Util qw(looks_like_number);

sub hostname_by_num { 
    my $num = shift;

    # validate our argument
    defined $num
       or return undef;
    $num >= 1
       or return undef;
    looks_like_number( $num )
       or return undef;

    $num--;  # convert into array index.

    return exists $HOSTS[$num] ? $HOSTS[$num] : undef;
}
[download]

Now you can simplify choose_host.

sub choose_host {
    my $chosen_host;
    while ( !defined $chosen_host ) {
        printchoices();
        $chosen_host = hostname_by_num( getchoice() );
    }

    return $chosen_host;
}

# for loop can now be:
sub printchoices {
    print join "\n",
        "\n",
        "ssh hosts",
        "-"x8;

    foreach my $host_num ( 1..num_hosts() ) {
        print "[$host_num] ", hostname_by_num($host_num), "\n" ;
    }
}
[download]

The concatenation in ssh_string is hard to read, try join with a null string for assembling the return value:

sub ssh_string {
    my $host = shift;
  
    return join '',
        username(),
        '@', 
        $host,
        domain();
}
[download]

Also, ditch the unneeded & sigil from your subroutine calls. It can have unexpected consequences. See perlsub.

Update: The relevent bits from perlsub, with emphasis added:

...If a subroutine is called using the & form, the argument list is optional, and if omitted, no @_ array is set up for the subroutine: the @_ array at the time of the call is visible to subroutine instead. This is an efficiency mechanism that new users may wish to avoid.
...
Not only does the & form make the argument list optional, it also disables any prototype checking on arguments you do provide. This is partly for historical reasons, and partly for having a convenient way to cheat if you know what you're doing. See Prototypes below.